// 给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
// 子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。
// 例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
// 来源：力扣（LeetCode）
// 链接：https://leetcode.cn/problems/longest-increasing-subsequence
// 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

/**
 * @param {number[]} nums
 * @return {number}
 */
var lengthOfLIS = function (nums) {
  const len = nums.length

  // 1. dp[i] 的含义是，以 nums[i] 结尾子序列的最大长度
  const dp = new Array(len).fill(1)
  // 明确 dp 数组的定义。
  // 这一步对于任何动态规划问题都很重要，
  // 如果不得当或者不够清晰，会阻碍之后的步骤。
  // 如果觉得当前 dp 数组的定义没法写出第二步
  // 那么要及时更换 dp 数组的定义

  // 2. dp[i] => dp[j]，其中 nums[j] < nums[i]
  for (let i = 0; i < len; i++) {
    for (let j = 0; j < i; j++) {
      if (nums[i] > nums[j]) {
        dp[i] = Math.max(dp[j] + 1, dp[i])
      }
    }
  }

  // 3. 寻找最大的长度
  return Math.max(...dp)
}

console.log(
  lengthOfLIS([0, 1, 0, 3, 2, 3])
)

